recursive types

A hợp_nhất or kiểu may name itself in its own fields; every backend gives it a finite carrier.

Syntax: hợp_nhất <name> { <Variant> { <name> <field> } } · kiểu <name> { <name> ∪ rỗng_ty <field> }

Category#

type

Related#

• hợp_nhất
• kiểu
• phân_tích
• tạo
• rỗng

Examples#

radix/corpus/recursio/expressio-arbor.fab (canonical · feature)#

A hợp_nhất or kiểu may name itself in its own fields; every backend gives it a finite carrier.

# =============================================================================
# recursive types — a type may refer to itself in its own fields.
# =============================================================================
#
# What this teaches:
#   • Recursive hợp_nhất — `Expr` variants hold `Expr` operands, so a value
#     is a whole expression tree. `phân_tích` walks it recursively.
#   • Recursive kiểu — `Nodus` holds a nullable `Nodus` link, so a value is a
#     linked list ending in `rỗng_ty`.
#   • No keyword, no box type — Faber values alias by reference, so the
#     indirection is implied. Backends that store fields inline (Rust) insert
#     the pointer themselves on the fields that close the cycle.
#
# Common mistakes:
#   • A non-nullable self field on a kiểu (`Nodus next`) — no value can ever
#     be built, because every node needs another node. End the chain with
#     `∪ rỗng_ty`, or recurse through a hợp_nhất with a leaf variant.
#
# See also: hợp_nhất, kiểu, phân_tích, tạo, rỗng_ty
# =============================================================================
#
# EXPECTED OUTPUT:
#   14
#   (2 + (3 * 4))
#   -9
#   6
#   3
#   2
#   15

union Expr {
    Numerus {
        int giá_trị
    },
    Nega {
        Expr interior
    },
    Adde {
        Expr sinister
        Expr dexter
    },
    Multiplica {
        Expr sinister
        Expr dexter
    }
}

fn evalua(Expr e) → int {
    match e {
        case Numerus const giá_trị {
            return giá_trị
        }
        case Nega const interior {
            return 0 - evalua(interior)
        }
        case Adde const sinister, dexter {
            return evalua(sinister) + evalua(dexter)
        }
        case Multiplica const sinister, dexter {
            return evalua(sinister) * evalua(dexter)
        }
    }
}

fn depinge(Expr e) → string {
    match e {
        case Numerus const giá_trị {
            return "§"(giá_trị)
        }
        case Nega const interior {
            return "-§"(depinge(interior))
        }
        case Adde const sinister, dexter {
            return "(§ + §)"(depinge(sinister), depinge(dexter))
        }
        case Multiplica const sinister, dexter {
            return "(§ * §)"(depinge(sinister), depinge(dexter))
        }
    }
}

class Nodus {
    var int giá_trị
    var Nodus ∪ none sequens
}

fn tổng(Nodus ∪ none n) → int {
    if n is none {
        return 0
    }
    return n.valor + tổng(n.sequens)
}

fn longitudo(Nodus ∪ none n) → int {
    if n is none {
        return 0
    }
    return 1 + longitudo(n.sequens)
}

main {
    const Expr tres ← variant Numerus { giá_trị = 3 }
    const Expr productum ← variant Multiplica { sinister = tres, dexter = variant Numerus { giá_trị = 4 } }
    const Expr arbor ← variant Adde { sinister = variant Numerus { giá_trị = 2 }, dexter = productum }
    print evalua(arbor)
    print depinge(arbor)
    print evalua(variant Nega { interior = variant Adde { sinister = tres, dexter = variant Numerus { giá_trị = 6 } } })

    var Nodus caput ← Nodus { giá_trị = 1, sequens = Nodus { giá_trị = 2, sequens = Nodus { giá_trị = 3, sequens = null } } }
    print tổng(caput)
    print longitudo(caput)
    print caput?.sequens?.valor
    caput.sequens ← Nodus { giá_trị = 14, sequens = null }
    print tổng(caput)
}

Expected output:

14
(2 + (3 * 4))
-9
6
3
2
15